package 力扣题库;

import 剑指offer.ListNode;

import java.util.HashSet;
import java.util.Set;

public class p141环形链表 {
    public boolean hasCycle1(ListNode head) {
        //哈希表
        Set<ListNode> set=new HashSet<>();

        while (head!=null) {
            if (set.contains(head)) {
                return true;
            }
            set.add(head);
            head=head.next;
        }

        return false;
    }

    public boolean hasCycle2(ListNode head) {
        //快慢指针
        if (head==null || head.next==null) {
            return false;
        }
        ListNode fast=head.next;
        ListNode slow=head;

        while (fast!=slow) {
            if (fast==null || fast.next==null) {
                return false;
            }
            fast=fast.next.next;
            slow=slow.next;
        }
        return true;
    }

    public boolean hasCycle(ListNode head) {
        //快慢指针，快指针比慢指针快一步
        ListNode fast=head;
        ListNode slow=head;

        while (fast!=null && fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if (slow==fast) {
                return true;
            }
        }
        //链表中没有环
        return false;
    }
}
